package cn.cxq.learning.single_linked_list;

import java.util.HashSet;

/**
 * 剑指offer
 * 链表中环的入口结点
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：409190
 * 本题知识点： 链表
 *  算法知识视频讲解
 * 题目描述
 * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
 * 说明：本题目包含复杂数据结构ListNode，点此查看相关信息
 */
public class EntryNodeOfLoop {

    // 双指针法
    // 思路： 用fast指针和slow指针一个一次移动两个节点一个一次移动一个节点算出两倍路程，
    // 然后fast指针归头节点，两个指针每次移动一个节点，再次相遇就是环的入口了
    public ListNode EntryNodeOfLoop(ListNode pHead) {

        if (pHead.next == null) {
            return null;
        }

        ListNode fast = pHead.next.next;
        ListNode slow = pHead.next;

        while (fast != null) {

            if (fast == slow) {
                break;
            }

            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                break;
            }

            slow = slow.next;
        }

        if (fast == null) {
            return null;
        }

        fast = pHead;

        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }


    // 哈希法（判断是否有节点重复）
//    public ListNode EntryNodeOfLoop(ListNode pHead) {
//
//        HashSet<ListNode> listNodes = new HashSet<>();
//
//        ListNode cur = pHead;
//
//        while (cur != null) {
//            if (listNodes.contains(cur)) {
//                return cur;
//            }
//            listNodes.add(cur);
//            cur = cur.next;
//        }
//
//        return null;
//    }
}
